from collections import Counter
from collections import defaultdict
from typing import List


class Solution:

    def __init__(self):
        self.ans = 0
        self.graph = defaultdict(dict)
        self.max_time = 0
        self.values = []
        self.visited = Counter()

    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        self.values = values
        for u, v, time in edges:
            self.graph[u][v] = time
            self.graph[v][u] = time
        self.max_time = maxTime
        # print("MAX_TIME:", self.max_time)

        self.visited[0] += 1
        self.dfs(0, values[0], 0)

        return self.ans

    def dfs(self, cur_point, cur_val, cur_time):
        # print("CUR:", cur_point, cur_val, cur_time)
        if cur_point == 0:
            self.ans = max(self.ans, cur_val)
        for nxt_point, need_time in self.graph[cur_point].items():
            nxt_time = cur_time + need_time

            if self.visited[nxt_point] == 0:
                nxt_val = cur_val + self.values[nxt_point]
            else:
                nxt_val = cur_val

            self.visited[nxt_point] += 1

            if nxt_time <= self.max_time:
                self.dfs(nxt_point, nxt_val, nxt_time)

            self.visited[nxt_point] -= 1


if __name__ == "__main__":
    # 75
    print(Solution().maximalPathQuality(values=[0, 32, 10, 43], edges=[[0, 1, 10], [1, 2, 15], [0, 3, 10]], maxTime=49))

    # 25
    print(Solution().maximalPathQuality(values=[5, 10, 15, 20], edges=[[0, 1, 10], [1, 2, 10], [0, 3, 10]], maxTime=30))

    # 7
    print(Solution().maximalPathQuality(values=[1, 2, 3, 4], edges=[[0, 1, 10], [1, 2, 11], [2, 3, 12], [1, 3, 13]],
                                        maxTime=50))

    # 0
    print(Solution().maximalPathQuality(values=[0, 1, 2], edges=[[1, 2, 10]], maxTime=10))
